//
// Created by ASUS on 2025/1/3/星期五.
//
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int l,r;
	int lazy=0;
	int mx=0;
	Node*left=nullptr,*right=nullptr;
	Node(int _l,int _r):l(_l),r(_r){};
};

void pushUp(Node* node) {
	node->mx = max(node->left? node->left->mx : 0, node->right? node->right->mx : 0);
}

void pushDown(Node* node) {
	if (node->lazy) {
		if (!node->left) node->left = new Node(node->l, (node->l + node->r) / 2);
		if (!node->right) node->right = new Node((node->l + node->r) / 2 + 1, node->r);
		node->left->mx += node->lazy;
		node->left->lazy += node->lazy;
		node->right->mx += node->lazy;
		node->right->lazy += node->lazy;
		node->lazy = 0;
	}
}

// 区间更新
void update(Node* node, int L, int R, int val) {
	if (L <= node->l && node->r <= R) {
		node->mx += val;
		node->lazy += val;
		return;
	}
	pushDown(node);
	int mid = (node->l + node->r) / 2;
	if (L <= mid) {
		if (!node->left) node->left = new Node(node->l, mid);
		update(node->left, L, R, val);
	}
	if (R > mid) {
		if (!node->right) node->right = new Node(mid + 1, node->r);
		update(node->right, L, R, val);
	}
	pushUp(node);
}

// 区间查询
int query(Node* node, int L, int R) {
	if (L <= node->l && node->r <= R) {
		return node->mx;
	}
	pushDown(node);
	int mid = (node->l + node->r) / 2;
	int res = 0;
	if (L <= mid) {
		if (node->left) res = max(res, query(node->left, L, R));
	}
	if (R > mid) {
		if (node->right) res = max(res, query(node->right, L, R));
	}
	return res;
}